// https://leetcode.cn/problems/possible-bipartition/
// Created by ade on 2022/10/19.
//
#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    // 思考：每个人只能被标记成颜色1或者2，如果标记成功则ok
    // 参考：https://leetcode.cn/problems/possible-bipartition/solution/by-heroding-1yeh/
    vector<int> colors = {}; // 当前下标是否染色
    vector <vector<int>> dislike_arr = {}; // 每个下标不喜欢的
    bool possibleBipartition(int n, vector <vector<int>> &dislikes) {
        colors.resize(n + 1, 0);
        dislike_arr = vector < vector < int >> (n + 1);

        // 标记每个人的不喜欢的数组
        for (auto &item:dislikes) {
            dislike_arr[item[0]].push_back(item[1]);
            dislike_arr[item[1]].push_back(item[0]);
        }
        // 遍历每个人
        for (int i = 1; i <= n; i++) {
            // 默认标记为颜色1
            if (colors[i] == 0 && !dfs(i, 1)) {
                return false;
            }
        }
        return true;
    }

    bool dfs(int node, int color) {
        colors[node] = color;

        for (auto &dislike_node : dislike_arr[node]) {
            // 遍历不喜欢的，如果比喜欢的颜色和自己相同，则返回false
            if (colors[dislike_node] == color) {
                return false;
            }
            // 同样操作，对于不喜欢的人，染色另一种
            if (colors[dislike_node] == 0 && !dfs(dislike_node, 3 ^ color)) {
                return false;
            }
        }
        return true;
    }
};


int main() {
    Solution so;
    vector <vector<int>> arr = {{1, 2},
                                {1, 3},
                                {2, 4}};
    int a = so.possibleBipartition(4, arr);
    cout << a << endl;
    return 0;
}